
#include <iostream>
#include <fstream>
#include "sqlist.h"

using namespace std;

typedef sqlisttpl<int> sqlist;

sqlist &intersection( sqlist &, sqlist & );
sqlist &intersection2( sqlist &, sqlist & );
sqlist &intersection3( sqlist &, sqlist & );

int main()
{
    ifstream in( "in.txt" );
    vector<int> va, vb;
    sqlist sa, sb, sc;
    int i, n;
    int t;

    in >> n;
    for ( i = 0; i < n; i++ ){
	in >> t;
	va.push_back(t);
    }

    in >> n;
    for ( i = 0; i < n; i++ ){
	in >> t;
	vb.push_back(t);
    }

    sa.create( va );
    sa.print(); cout << endl;
    sb.create( vb );
    sb.print(); cout << endl;

    sc = intersection3( sa, sb );
    sc.print(); cout << endl;

    return 0;
}


/* ******************************************************
 *             Answer to this question.
 * ******************************************************/

//has some problem
sqlist &intersection( sqlist &a, sqlist &b )
{
    int i, j, p, q;
    int t;
		
    i = j = 0;
    while( i < a.length() ){
	
	while( j<b.length() && b[j]<a[i] ) j++;
	t = a[i];
	if( b[j] == a[i] ) i++;	
	q = i;
	while( q < a.length() && a[q] == t ) q++;
	p = i;
	while( q < a.length() ) a[p++] = a[q++];
	a.inc(q-p);			
	
    }
    
    return a;
}

//has some problem
sqlist &intersection2( sqlist &a, sqlist &b )
{
    int i, j, k, t;
    
    i = j = k = 0;
    while( i<a.length() && j<b.length() ){
	
	if( a[i] < b[j] ) i++;
	else if( a[i] > b[j] ) j++;
	else{
	    while( i < a.length() && a[i]==b[j] ) i++;
	    i--;
	    t = k;
	    while( i < a.length() ) a[t++] = a[i++];
	    a.inc(i-t);
	    i = ++k; 
	}
	
    }
    
    return a;
}

//has some problem
sqlist &intersection3( sqlist &a, sqlist &b )
{
    int i, j, k;
	
    i = j = 0;
    k = -1;
    while( i<a.length() && j<b.length() ){
	
	if( a[i] < b[j] ) i++;
	else if( a[i] > b[j] ) j++;
	else{
	    if( k == -1 || a[k] != a[i] ) a[++k] = a[i];
	    i++, j++;
	}
		
    }
    a.inc(a.length()-k-1);
    
    return a;
}

